package leetcode.editor.offer;

// 剑指 Offer 62. 圆圈中最后剩下的数字
// https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
class YuanQuanZhongZuiHouShengXiaDeShuZiLcof {
    public static void main(String[] args) {
        Solution solution = new YuanQuanZhongZuiHouShengXiaDeShuZiLcof().new Solution();
        solution.lastRemaining(5, 3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lastRemaining(int n, int m) {
            // 模拟超时
            /*LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                list.add(i);
            }

            int idx = 0;
            while (list.size() != 1) {
                idx = (idx + m - 1) % list.size();
                list.remove(idx);
            }

            return list.get(0);*/

            // 动态规划
            /**
             *         第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
             *         (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
             *         第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
             *         第三次，【1, 3, 4】，本轮要踢出4                                        看1
             *         第四次，【1, 3】 本轮要踢出1                                            看3
             *         第五次，【3】
             *         最后返回3
             *
             *         我们要使用的数学方法，就是从结果0号位置，反推最开始在哪
             *         你从第二次，向上看第一次
             *         你会发现，原来3在0的位置
             *                 现在，3在(0 + 3) % 5
             *                         => +3 回到上次的位置
             *                         => %5 防止数组溢出，并且数组本来就是循环数组
             *          也就是我们需要找到最后数字最原先的位置。倒推回去。
             *
             *         f(n) = ( f(n - 1) + m ) % n
             *         解释意思：
             *             f(n) 表示上一次
             *             f(n - 1) 表示这次，因为我们要从这次回推上一次
             *             m 表示隔几个
             *             n表示上一次的数组长度
             */
            int x = 0;
            for (int i = 2; i <= n; i++) {
                x = (x + m) % i;
            }

            return x;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
